백준 30805번
오늘 풀어본 문제는 백준의 30805번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
어떤 수열이 다른 수열의 부분 수열이라는 것은 다음을 의미합니다.
- 해당 수열의 원소들이 다른 수열 내에서 순서대로 등장합니다.
- 예를 들어, ${1,1,5}$ 는 ${3,\underline{\color{blue} 1} ,4,\underline{\color{blue} 1} ,\underline{\color{blue} 5} ,9}$ 의 부분 수열이지만, ${1,5,1}$ 의 부분 수열은 아닙니다.
또한, 어떤 수열이 다른 수열보다 사전 순으로 나중이라는 것은 다음을 의미합니다.
- 두 수열 중 첫 번째 수가 큰 쪽은 사전 순으로 나중입니다.
- 두 수열의 첫 번째 수가 같다면, 첫 번째 수를 빼고 두 수열을 다시 비교했을 때 사전 순으로 나중인 쪽이 사전 순으로 나중입니다.
- 길이가 $0$ 인 수열과 다른 수열을 비교하면, 다른 수열이 사전 순으로 나중입니다.
양의 정수로 이루어진 길이가 $N$ 인 수열 ${A_1,\cdots ,A_N}$ 이 주어집니다. 마찬가지로 양의 정수로 이루어진 길이가 $M$ 인 수열 ${B_1,\cdots ,B_M}$ 이 주어집니다.
수열 $A$ 와 수열 $B$ 가 공통으로 갖는 부분 수열들 중 사전 순으로 가장 나중인 것을 구하세요.
입력
첫 줄에 수열 $A$ 의 길이 $N$ 이 주어집니다. $(1 \le N \le 100)$
둘째 줄에 $N$ 개의 양의 정수 $A_1,A_2,\cdots,A_N$ 이 주어집니다. $(1 \le A_i \le 100)$
셋째 줄에 수열 $B$ 의 길이 $M$ 이 주어집니다. $(1 \le M \le 100)$
넷째 줄에 $M$ 개의 양의 정수 $B_1,B_2,\cdots,B_M$ 이 주어집니다.
출력
$A$ 와 $B$ 의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 크기 $K$ 를 출력하세요.
$K \ne 0$ 이라면, 다음 줄에 $K$ 개의 수를 공백으로 구분해 출력하세요. $i$ 번째 수는 $A$ 와 $B$ 의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 $i$ 번째 수입니다.
풀이과정
1번째 시도
문제의 이름을 보고 LCS (Longest Common Subsequence) 알고리즘을 활용하면 되는 문제라고 추측했다.
내가 사용한 방식은 기존의 LCS를 찾는 알고리즘을 이용하여 LCS를 찾은 뒤, 그중 가장 큰 수부터 수열이 시작되도록 자른 뒤 그 수열을 답으로 출력하게 하는 방식이다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<int> A(N, 0);
for (int i=0; i<N; i++) {
cin >> A[i];
}
int M;
cin >> M;
vector<int> B(M, 0);
for (int i=0; i<M; i++) {
cin >> B[i];
}
vector<vector<int>> dp(N+1, vector<int>(M+1, 0));
for (int i=1; i<=N; i++) {
for (int j=1; j<=M; j++) {
if (A[i-1] == B[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
vector<int> result;
if (dp[N][M] != 0) {
int i = N;
int j = M;
while (i > 0 && j > 0) {
if (A[i-1] == B[j-1]) {
result.emplace_back(A[i-1]);
i--;
j--;
}
else {
if (dp[i-1][j] > dp[i][j-1]) {
i--;
}
else {
j--;
}
}
}
reverse(result.begin(), result.end());
int maximum = 0;
int largestIndex = 0;
for (int i=0; i<N; i++) {
if (maximum < result[i]) {
maximum = result[i];
largestIndex = i;
}
}
cout << result.size() - largestIndex << "\n";
for (int i=largestIndex; i<result.size(); i++) {
cout << result[i] << " ";
}
}
else {
cout << 0;
}
return 0;
}
실행 결과 ‘틀렸습니다’ 가 떴다.
2번째 시도
이전 제출에서 내가 간과한 부분으로 떠올린 것은, LCS의 부분 수열 중 사전 순으로 가장 앞서는 것이 꼭 연속적으로 나열된 부분 수열일 필요가 없다는 것이었다.
예를 들어 LCS가 ${3,\ 1,\ 2}$ 라고 하면, 이전 제출의 경우 연속적으로 나열된 부분 수열만을 추출하기 때문에 ${3,\ 1}$ 을 얻어내지만, 실제로 사전 순으로 가장 앞서는 것은 ${3,\ 2}$ 로, 제대로 된 결과를 얻어내지 못하는 것이다.
이를 해결하기 위해서 LCS를 구한 뒤 LCS의 부분 수열을 추출하는 과정을 수정하였다. std::stack 을 활용하여 큰 수들을 최대한 앞쪽으로 배치하도록 하여 사전 순으로 가장 앞서는 것을 찾을 수 있게 하였다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<int> A(N, 0);
for (int i=0; i<N; i++) {
cin >> A[i];
}
int M;
cin >> M;
vector<int> B(M, 0);
for (int i=0; i<M; i++) {
cin >> B[i];
}
vector<vector<int>> dp(N+1, vector<int>(M+1, 0));
for (int i=1; i<=N; i++) {
for (int j=1; j<=M; j++) {
if (A[i-1] == B[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
vector<int> lcs;
if (dp[N][M] != 0) {
int i = N;
int j = M;
while (i > 0 && j > 0) {
if (A[i-1] == B[j-1]) {
lcs.emplace_back(A[i-1]);
i--;
j--;
}
else {
if (dp[i-1][j] > dp[i][j-1]) {
i--;
}
else {
j--;
}
}
}
reverse(lcs.begin(), lcs.end());
stack<int> result;
result.push(lcs[0]);
for (int i=1; i<lcs.size(); i++) {
if (result.top() < lcs[i]) {
while (!result.empty() && result.top() < lcs[i]) {
result.pop();
}
}
result.push(lcs[i]);
}
cout << result.size() << "\n";
vector<int> finalResult;
while (!result.empty()) {
finalResult.emplace_back(result.top());
result.pop();
}
reverse(finalResult.begin(), finalResult.end());
for (auto& i : finalResult) {
cout << i << " ";
}
}
else {
cout << 0;
}
return 0;
}
실행 결과 ‘틀렸습니다’ 가 떴다.
3번째 시도
LCS를 활용한 2개의 제출이 모두 실패했고, 질문 게시판을 이용하여 반례를 살펴본 결과 애초에 이 문제에서 답을 구할 때 LCS의 부분 수열중에는 답이 없을 수 있다는 결론에 도달하게 되었다.
3번째 제출부터 선택한 새로운 방식은, $A$ 수열과 $B$ 수열의 범위가 1부터 100 사이라는 점을 이용하여 타겟을 100부터 1로 줄여나가면서 각 수열과 일치하는 것이 있는지 확인하고, 있다면 타겟을 정답 수열에 포함시킨 뒤, 각 수열에서 발견된 위치 이후의 인덱스 부터 다시 탐색을 진행하는 방식을 이용하게 하였다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<int> A(N);
for (int i=0; i<N; i++) {
cin >> A[i];
}
int M;
cin >> M;
vector<int> B(M);
for (int i=0; i<M; i++) {
cin >> B[i];
}
vector<int> result;
int startA = 0;
int startB = 0;
for (int target=100; target>0; target--) {
bool found = false;
for (int i=startA; i<N; i++) {
if (A[i] == target) {
for (int j=startB; j<M; j++) {
if (B[j] == target) {
result.emplace_back(target);
startA = i+1;
startB = j+1;
found = true;
break;
}
}
}
if (found) break;
}
}
cout << result.size() << "\n";
for (auto& i : result) {
cout << i << " ";
}
return 0;
}
실행 결과 ‘틀렸습니다’ 가 떴다.
4번째 시도
3번째 제출에서 간과한 부분은 정답 수열에 같은 수가 여러 번 나올 수 있다는 것이었다. 지금과 같은 방식으로는 100부터 1까지 정답 수열에 한 번씩만 나오게 할 수 있는데, 이 때문에 실제 정답과 차이가 발생할 수 있는 것이었다.
이를 해결하기 위해 사용한 방식은 기존의 3중 반복문에 반복문을 하나 더 씌워 중복된 수도 검출해낼 수 있게 하는 것이었다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<int> A(N);
for (int i=0; i<N; i++) {
cin >> A[i];
}
int M;
cin >> M;
vector<int> B(M);
for (int i=0; i<M; i++) {
cin >> B[i];
}
vector<int> result;
int startA = 0;
int startB = 0;
while (startA < N && startB < M) {
bool found = false;
for (int target=100; target>0; target--) {
for (int i=startA; i<N; i++) {
if (A[i] == target) {
for (int j=startB; j<M; j++) {
if (B[j] == target) {
result.emplace_back(target);
startA = i+1;
startB = j+1;
found = true;
break;
}
}
}
if (found) break;
}
if (found) break;
}
}
cout << result.size() << "\n";
for (auto& i : result) {
cout << i << " ";
}
return 0;
}
실행 결과 ‘시간 초과’가 떴다.
5번째 시도
4번째 시도에서 시간 초과가 발생한 것은 시간 복잡도가 너무 커져버렸기 때문이라고 생각했다.
그래서 3번째 제출때의 코드를 이번에는 중간에 같은 수가 발견되었다고해서 바로 빠져나오지 않고 계속 타겟값을 유지시킨 뒤 탐색을 진행하도록 해보았다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<int> A(N);
for (int i=0; i<N; i++) {
cin >> A[i];
}
int M;
cin >> M;
vector<int> B(M);
for (int i=0; i<M; i++) {
cin >> B[i];
}
vector<int> result;
int startA = 0;
int startB = 0;
for (int target=100; target>0; target--) {
for (int i=startA; i<N; i++) {
if (A[i] == target) {
for (int j=startB; j<M; j++) {
if (B[j] == target) {
result.emplace_back(target);
startA = i+1;
startB = j+1;
break;
}
}
}
}
}
cout << result.size() << "\n";
for (auto& i : result) {
cout << i << " ";
}
return 0;
}
그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.
마무리
오랫동안 CLASS 4 문제를 풀지 않았기 때문에 CLASS 4 만의 매운맛을 잊고 있었다! 애초에 기존에 알던 LCS 알고리즘을 무조건 이용해야 한다고 착각했던 것이 가장 큰 문제점이었던 것 같다…
어쨌거나 솔브드 업데이트로 인해 뺏겼던 CLASS 4 금장을 다시 되찾는데 성공하였다!
이제 남은 건 CLASS 5 은장과 금장이다. 예전의 영광을 되찾기 위해서는 열심히 노력해야 할 것 같다…
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/30805